package com.example.demo.arithmetic.datastructure.linkedlist;

import java.util.Iterator;
import java.util.Stack;

/**
 * @Description:
 * @Author: LLL
 * @Date: 2020-03-13 20:28
 **/
public class SingleLinkedList {

    /**
     * 头指针 不存放有效数据
     */
    private HeroNode head = new HeroNode("", "", 0);

    /**
     * @param add 添加至尾部
     */
    public void add(HeroNode add) {
        // 1.寻找最后一个节点
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            } else {
                temp = temp.next;
            }
        }
        // 2.next指向要添加的节点
        temp.next = add;
    }

    /**
     * @param add 添加至合适的位置
     */
    public void addByOrder(HeroNode add) {
        // 1.寻找要添加的位置

        // 2.add.next = temp.next

        // 3.temp.next = add
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > add.no) {
                break;
            } else if (temp.next.no == add.no) {
                flag = true;//编号存在
                break;
                //                throw new RuntimeException("node is exist!!!");
            }
            temp = temp.next;// 遍历
        }
        // 2.next指向要添加的节点
        if (!flag) {
            add.next = temp.next;
            temp.next = add;
        } else {
            System.out.printf("编号%d已存在，不可加\n", add.no);
        }
    }

    /**
     * 打印链表数据
     */
    public void list() {
        //            if (head.next == null) {
        //                return;
        //            }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    public void update(HeroNode nNode) {
        if (isEmpty()) {
            System.out.println("链表为空！");
            return;
        }
        // 找到需要修改的节点
        HeroNode temp = head.next;
        // 是否找到
        boolean flag = false;
        while (true) {
            if (temp == null) { // 遍历结束
                break;
            }
            // 从头开始遍历
            if (temp.no == nNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = nNode.name;
            temp.nickname = nNode.nickname;
        } else {
            System.out.println("没有匹配的修改项！");
        }

    }

    public boolean isEmpty() {
        return head.next == null;
    }

    /**
     * @Description:
     * @Param: * @param dNode
     * @return: void
     * @Author: liull
     * @Date: 2020/3/13
     */
    public void delete(HeroNode dNode) {
        // 1.找到需要删除的这个节点的前一个节点temp

        // 2.temp.next = temp.next.next

        if (isEmpty()) {
            System.out.println("链表为空！");
            return;
        }
        // 找到需要修改的节点
        HeroNode temp = head;
        // 是否找到
        boolean flag = false;
        while (true) {
            if (temp.next == null) { // 遍历结束
                break;
            }
            // 从头开始遍历
            if (temp.next.no == dNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有匹配的删除项！");
        }

    }

    /**
     * @Description: 大小
     * @Param: * @param
     * @return: int
     * @Author: liull
     * @Date: 2020/3/13
     */
    public int size() {
        HeroNode temp = head;
        int count = 0;
        while (temp.next != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }

    /**
     * @Description: 获取倒数第m个
     * @Param: * @param m
     * @return: void
     * @Author: liull
     * @Date: 2020/3/13
     */
    public HeroNode getLastM(int m) {
        int size = size();
        if (m < 0 || m > size) {
            return null;
        }
        HeroNode curr = head.next;
        for (int i = 0; i < size - m; i++) {
            curr = curr.next;
        }
        return curr;
    }

    /**
     * @Description: 实现链表翻转 三指针算法 1 指向当前节点 curr ;2 保存当前节点的下一节点 next ;3 指向新链表表头保存结果
     * @Param: * @param
     * @return: void
     * @Author: liull
     * @Date: 2020/3/13
     */
    public void reverse() {
        // 从第一个节点开始
        HeroNode curr = head.next;
        // 没有第一个节点或者只有一个节点直接返回
        if (curr == null || size() == 1) {
            return;
        }
        // 1.新建一个新的head
        HeroNode reverseHead = new HeroNode("", "", 0);
        // 指向当前节点的下一个节点
        HeroNode next = null;
        // 2.遍历原来的链表，遍历一个就取出，放在新的链表的最前端
        while (curr != null) {
            // 先保存当前节点下一节点
            //            next = curr.next;
            // 将当前节点下一节点方法指向新的链表的最前端
            curr.next = reverseHead.next;
            reverseHead.next = curr;
            // 往后遍历
            curr = curr.next;
        }
        head.next = reverseHead.next;
    }

    public void listFromRear() {
        HeroNode curr = head.next;
        if (curr == null) {
            return;
        }
        // 创建Stack
        Stack<HeroNode> stack = new Stack<>();
        while (curr != null) {
            stack.add(curr);
            curr = curr.next;
        }
        Iterator<HeroNode> iterator = stack.iterator();
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

}
